package medium;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * 767. 重构字符串
 * 创建时间：2024-05-16 22:00
 * 地址：https://leetcode.cn/problems/reorganize-string/description/
 **/
public class 重构字符串_767 {
    static class Solution {
        public String reorganizeString(String s) {
            int max = 0;
            int sum = s.length();
            Map<Character, Integer> map = new HashMap<>();
            for (char c : s.toCharArray()) {
                map.merge(c, 1, Integer::sum);
                max = Math.max(map.get(c), max);
            }
            //排序
            List<Map.Entry<Character, Integer>> list = new ArrayList<>(map.entrySet());
            list.sort((q, p) -> p.getValue() - q.getValue());
            // 这种情况不会有结果
            if (max > sum - max + 1) {
                return "";
            }

            char[] ans = new char[sum];
            // 从偶数开始填入
            int index = 0;
            for (Map.Entry<Character, Integer> entry : list) {
                Integer value = entry.getValue();
                while (value-- > 0) {
                    ans[index] = entry.getKey();
                    index += 2;
                    if (index >= sum) {
                        index = 1;
                    }
                }
            }
            return new String(ans);
        }
    }
}
